package com.fanshuai2.niuke.search.dfs;

import java.util.*;

/**
 * 给定一个正整数N代表火车数量，0<N<10，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号，火车站只有一个方向进出，同时停靠在火车站的列车中，只有后进站的出站了，先进站的才能出站。
 * 要求输出所有火车出站的方案，以字典序排序输出。
 *
 * 输入描述：
 * 第一行输入一个正整数N（0 < N <= 10），第二行包括N个正整数，范围为1到10。
 *
 * 输出描述：
 * 输出以字典序从小到大排序的火车出站序列号，每个编号以空格隔开，每个输出序列换行，具体见sample。
 *
 * 输入：
 * 3
 * 1 2 3
 * 输出：
 * 1 2 3
 * 1 3 2
 * 2 1 3
 * 2 3 1
 * 3 2 1
 * 说明：
 * 第一种方案：1进、1出、2进、2出、3进、3出
 * 第二种方案：1进、1出、2进、3进、3出、2出
 * 第三种方案：1进、2进、2出、1出、3进、3出
 * 第四种方案：1进、2进、2出、3进、3出、1出
 * 第五种方案：1进、2进、3进、3出、2出、1出
 * 请注意，[3,1,2]这个序列是不可能实现的。
 */
public class Railway {
    static List<String> getOutput(int[] railway) {
        Stack<Integer> stack = new Stack<>();
        List<String> all = new ArrayList<>();

        output(railway, stack, 0, 0, "", all);
        Collections.sort(all);
        return all;
    }

    static void output(int[] railway, Stack<Integer> stack, int i, int n,
                       String out, List<String> all) {
        if (n == railway.length) {
            all.add(out);
            return;
        }

        if (i < railway.length) {
            stack.push(railway[i]);
            output(railway, stack, i + 1, n, out, all);
            stack.pop();
        }
        if (!stack.isEmpty()) {
            int value = stack.pop();
            output(railway, stack, i, n + 1, out + value + " ", all);
            stack.push(value);
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        while (in.hasNextInt()) {
            int n = in.nextInt();
            int[] railway = new int[n];
            for (int i = 0; i < n; i++) {
                railway[i] = in.nextInt();
            }

            List<String> s = getOutput(railway);
            for (String o : s) {
                System.out.println(o);
            }
        }
    }
}
